
require("util")

--[[
	defBrick = {
		originalBrickId,
		posRelTU, angleIdRel
		uiName, color, colorF
		brickSizeTUUnrotated, symmetry
		loadStringRotationAngleId
	}
	realBrick = {
		brickId,
		originalBrickId,
		posAbsTU, angleIdAbs
		uiName, color, colorFx
		brickSizeTUUnrotated, symmetry
		loadStringRotationAngleId
		realBrickString, partialString
	}
	node = see lower
	spot = {
		posAbsTU (origin of pattern that matches at spot)
		angleIdRot
	}
	canvas = {
		realBricksByRealBrickString = dict of realBrickString -> realBrick
		filledSpaceByPosAbsTUString = dict of posAbsTUString -> realBrick
		physicalRealBricks = dict of realBrickString -> realBrick
		realBricksByPartialString = dict of uiName -> (dict of brickId -> realBrick)
	}
]]

local maxTemplateWidth = 20
local adjacentBrickBoxExpansion = vector{0.1, 0.1, 0.1}
local colorSpace = 39
local colorFx = {
	none = 0,
	pearl = 1,
	chrome = 2,
	glow= 3,
	blink = 4,
	swirl = 5,
	rainbow = 6,
}
local colorFxIgnore = colorFx.swirl
local colorFxFill = colorFx.rainbow
ts.eval [[
function mj_createBrick(%uiname, %pos, %rot, %color, %colorFx) {
	%db = $uiNameTable[%uiname]; if(%db$="") { echo("no brick named \"" @ %uiname @ "\""); return; }
	%brick = new fxDtsBrick() {
		datablock = %db;
		angleId = %rot;
		colorId = %color;
		isPlanted = 1;
	};
	
	%brickgroup = BrickGroup_12878;
	%brickgroup.add(%brick);
	
	%brick.setTransform(%pos SPC "0 0 1" SPC (%rot*$pi/2));
	%brick.trustCheckFinished();
	%err = %brick.plant();
	
	if(%err==1 || %err==3 || %err==5) { %brick.delete(); return ""; }
	
	%brick.generated = true;
	%brick.mjGenerated = true;
	
	%brick.setColorFx(%colorFx);
	
	return %brick;
}
]]
local function physicalCreateRealBrick(realBrick)
	assert(realBrick.brickId == nil)
	local brickId = tonumber(ts.call("mj_createBrick",
		realBrick.staticData.uiName,
		realBrick.posAbsTU:tsString(),
		realBrick.angleIdAbs,
		realBrick.color,
		realBrick.colorFx
	))
	if brickId == 0 then brickId = nil end
	if not brickId then talk("Error placing brick "..realBrick.realBrickString) end
	realBrick.brickId = brickId
end
local function physicalDeleteRealBrick(realBrick)
	assert(realBrick.brickId ~= nil)
	ts.delete(realBrick.brickId)
	realBrick.brickId = nil
end

local function physicalUpdateCanvas(canvas)
	local oldBricks = canvas.physicalRealBricks
	local newBricks = canvas.realBricksByRealBrickString
	
	for oldRealBrickString, oldRealBrick in pairs(oldBricks) do
		if not newBricks[oldRealBrickString] then
			physicalDeleteRealBrick(oldRealBrick)
		end
	end
	
	for newRealBrickString, newRealBrick in pairs(newBricks) do
		if not oldBricks[newRealBrickString] then
			physicalCreateRealBrick(newRealBrick)
		end
	end
	
	canvas.physicalRealBricks = {}
	for newRealBrickString, newRealBrick in pairs(newBricks) do
		if newRealBrick.brickId then
			canvas.physicalRealBricks[newRealBrickString] = newRealBrick
		end
	end
end

local function posIsInBox(box, pos)
	return
		pos.x >= box[1].x and
		pos.y >= box[1].y and
		pos.z >= box[1].z and
		pos.x <= box[2].x and
		pos.y <= box[2].y and
		pos.z <= box[2].z
end
local function posAbsTUGetString(posAbsTU)
	return string.format("%i,%i,%i",
		math.round(posAbsTU.x* 4),
		math.round(posAbsTU.y* 4),
		math.round(posAbsTU.z*10)
	)
end
local function getAllPosInBoxAbsTU(boxAbsTU)
	local allPosAbsTU = {}
	for x = math.round(boxAbsTU[1].x* 4) + 1, math.round(boxAbsTU[2].x* 4) - 1, 2 do
	for y = math.round(boxAbsTU[1].y* 4) + 1, math.round(boxAbsTU[2].y* 4) - 1, 2 do
	for z = math.round(boxAbsTU[1].z*10) + 1, math.round(boxAbsTU[2].z*10) - 1, 2 do
		local posAbsTU = vector{x/4 , y/4 , z/10}
		table.insert(allPosAbsTU, posAbsTU)
	end
	end
	end
	return allPosAbsTU
end
local function getRealBrickBoxAbsTU(realBrick)
	local brickSizeTU = realBrick.staticData.brickSizeTUUnrotated:rotateAbs(realBrick.angleIdAbs)
	return {
		realBrick.posAbsTU - brickSizeTU/2,
		realBrick.posAbsTU + brickSizeTU/2,
	}
end
local function canvasRemoveRealBrick(canvas, realBrick)
	assert(canvas.realBricksByRealBrickString[realBrick.realBrickString] == realBrick)
	canvas.realBricksByRealBrickString[realBrick.realBrickString] = nil
	
	assert(canvas.realBricksByPartialString[realBrick.partialString][realBrick.realBrickString] == realBrick)
	canvas.realBricksByPartialString[realBrick.partialString][realBrick.realBrickString] = nil
	
	for _, posAbsTU in ipairs(getAllPosInBoxAbsTU(getRealBrickBoxAbsTU(realBrick))) do
		local posAbsTUString = posAbsTUGetString(posAbsTU)
		assert(canvas.filledSpaceByPosAbsTUString[posAbsTUString] == realBrick) -- fuck
		canvas.filledSpaceByPosAbsTUString[posAbsTUString] = nil
	end
end
local function canvasInsertRealBrick(canvas, realBrick)
	assert(canvas.realBricksByRealBrickString[realBrick.realBrickString] == nil, "Inserting duplicate brick "..realBrick.realBrickString) -- fuck
	canvas.realBricksByRealBrickString[realBrick.realBrickString] = realBrick
	
	assert(canvas.realBricksByPartialString[realBrick.partialString]==nil or canvas.realBricksByPartialString[realBrick.partialString][realBrick.brickId] == nil)
	if canvas.realBricksByPartialString[realBrick.partialString]==nil then canvas.realBricksByPartialString[realBrick.partialString] = {} end
	canvas.realBricksByPartialString[realBrick.partialString][realBrick.realBrickString] = realBrick
	
	for _, posAbsTU in ipairs(getAllPosInBoxAbsTU(getRealBrickBoxAbsTU(realBrick))) do
		local posAbsTUString = posAbsTUGetString(posAbsTU)
		canvas.filledSpaceByPosAbsTUString[posAbsTUString] = realBrick
	end
end

local function realBrickGetString(realBrick)
	return string.format("%s,%i,%i,%i,%s",
		realBrick.staticData.uiName,
		realBrick.color,
		realBrick.colorFx,
		realBrick.angleIdAbs % realBrick.staticData.symmetry,
		posAbsTUGetString(realBrick.posAbsTU)
	)
end
local function realBrickGetPartialString(realBrick)
	return string.format("%s,%i,%i",
		realBrick.staticData.uiName,
		realBrick.color,
		realBrick.colorFx
	)
end
local function createRealBrickFromDefBrick(defBrick, posAbsTU, angleIdRot)
	local realBrick = {
		posAbsTU = defBrick.posRelTU:rotate(angleIdRot) + posAbsTU,
		angleIdAbs = (defBrick.angleIdRel + angleIdRot) % 4,
		color = defBrick.color,
		colorFx = defBrick.colorFx,
		loadStringRotationAngleId = (defBrick.loadStringRotationAngleId + angleIdRot) % 4,
		staticData = defBrick.staticData,
	}
	realBrick.realBrickString = realBrickGetString(realBrick)
	realBrick.partialString = realBrickGetPartialString(realBrick)
	return realBrick
end

local patternGetRealBrickStrings = (function(patt, posAbsTU, angleIdRot, pos) -- memoize_multiarg
	local realBrickStrings = {}
	local posAbsTUs = {}
	for _, defBrick in ipairs(patt.defBricks) do
		local realBrick = createRealBrickFromDefBrick(defBrick, posAbsTU, angleIdRot)
		table.insert(realBrickStrings, realBrick.realBrickString)
		table.insert(posAbsTUs, realBrick.posAbsTU)
	end
	return realBrickStrings, posAbsTUs
end)
local spaceGetPosAbsTUStrings = (function(spacesRelTU, rootPosAbsTU, angleIdRot) -- memoize_multiarg
	local posAbsTUStrings = {}
	for _, posRelTU in ipairs(spacesRelTU) do
		local posAbsTU = posRelTU:rotate(angleIdRot) + rootPosAbsTU
		local posAbsTUString = posAbsTUGetString(posAbsTU)
		table.insert(posAbsTUStrings, posAbsTUString)
	end
	return posAbsTUStrings
end)
local spaceGetPosAbsTUs = (function(spacesRelTU, rootPosAbsTU, angleIdRot) -- memoize_multiarg
	local posAbsTUs = {}
	for _, posRelTU in ipairs(spacesRelTU) do
		local posAbsTU = posRelTU:rotate(angleIdRot) + rootPosAbsTU
		table.insert(posAbsTUs, posAbsTU)
	end
	return posAbsTUs
end)

local function patternGetRealBricks(canvas, patt, posAbsTU, angleIdRot)
	local realBricks = {}
	local realBrickStrings = patternGetRealBrickStrings(patt, posAbsTU, angleIdRot)
	for _, realBrickString in ipairs(realBrickStrings) do
		local realBrick = canvas.realBricksByRealBrickString[realBrickString]
		if realBrick then
			realBricks[realBrickString] = realBrick
		end
	end
	return realBricks
end
local function patternMatches(canvas, patt, posAbsTU, angleIdRot)
	if not posIsInBox(canvas.boxAbsTU, posAbsTU) then return false end
	
	local realBrickStrings, realBrickPosAbsTUs = patternGetRealBrickStrings(patt, posAbsTU, angleIdRot)
	
	for _, realBrickString in ipairs(realBrickStrings) do
		if not canvas.realBricksByRealBrickString[realBrickString] then return false end
	end
	
	local spacePosAbsTUStrings = spaceGetPosAbsTUStrings(patt.spacesRelTU, posAbsTU, angleIdRot)
	for _, spacePosAbsTUString in ipairs(spacePosAbsTUStrings) do
		if canvas.filledSpaceByPosAbsTUString[spacePosAbsTUString] then return false end
	end
	
	local fillPosAbsTUStrings = spaceGetPosAbsTUStrings(patt.fillsRelTU, posAbsTU, angleIdRot)
	for _, fillPosAbsTUString in ipairs(fillPosAbsTUStrings) do
		if not canvas.filledSpaceByPosAbsTUString[fillPosAbsTUString] then return false end
	end
	
	local newPosAbsTUs = spaceGetPosAbsTUs(patt.replaceSpacesRelTU, posAbsTU, angleIdRot)
	for _, newPosAbsTU in ipairs(newPosAbsTUs) do
		if not posIsInBox(canvas.boxAbsTU, newPosAbsTU) then return false end
	end
	
	return true
end
local function matchPattern(canvas, patt)
	local spots = {}
	if canvas.realBricksByPartialString[patt.rootBrick.partialString] then
		for _, realBrick in pairs(canvas.realBricksByPartialString[patt.rootBrick.partialString]) do
			for angleId = 0, 4 do
				assert(realBrick.posAbsTU)
				if patternMatches(canvas, patt, realBrick.posAbsTU, angleId) then
					local spot = {
						posAbsTU = realBrick.posAbsTU,
						angleIdRot = angleId,
					}
					table.insert(spots, spot)
				end
			end
		end
	end
	return spots
end

local function applyReplacement(canvas, spot, patt, repl)
	local oldRealBricks = patternGetRealBricks(canvas, patt, spot.posAbsTU, spot.angleIdRot)
	
	if not spot.posAbsTU then error("", 2) end
	
	local newRealBricks = {}
	for _, defBrick in ipairs(repl.defBricks) do
		local realBrick = createRealBrickFromDefBrick(defBrick, spot.posAbsTU, spot.angleIdRot)
		newRealBricks[realBrick.realBrickString] = realBrick
	end
	
	for realBrickString, realBrick in pairs(oldRealBricks) do
		if not newRealBricks[realBrickString] then
			canvasRemoveRealBrick(canvas, realBrick)
		end
	end
	
	for realBrickString, realBrick in pairs(newRealBricks) do
		if not oldRealBricks[realBrickString] then
			canvasInsertRealBrick(canvas, realBrick)
		end
	end
end

local function setCurrentNodeBricks(newTreeBrickIds)
	local oldNodeTreeBrickIds = MarkovJunior_Data.treeBricks
	
	for brickId, _ in pairs(newTreeBrickIds) do
		if not oldNodeTreeBrickIds[brickId] then
			if ts.isObject(brickId) then
				ts.callobj(brickId, "setColorFx", colorFx.glow)
			end
		end
	end
	for brickId, _ in pairs(oldNodeTreeBrickIds) do
		if not newTreeBrickIds[brickId] then
			if ts.isObject(brickId) then
				ts.callobj(brickId, "setColorFx", colorFx.none)
			end
		end
	end
	MarkovJunior_Data.treeBricks = newTreeBrickIds
end

local function selectByWeight(opts)
	local sum = 0
	for _, opt in ipairs(opts) do
		if not opt.choiceIgnore then
			sum = sum + opt.weight
		end
	end
	if sum==0 then return nil end
	
	local idx = math.random(1, sum)
	
	local sum2 = 0
	for _, opt in ipairs(opts) do
		if not opt.choiceIgnore then
			sum2 = sum2 + opt.weight
			if sum2 >= idx then return opt end
		end
	end
	error("how")
end

local applyNodeTypes
local function applyNode(canvas, node)
	setCurrentNodeBricks(node.treeBrickIds)
	local v = applyNodeTypes[node.type](canvas, node)
	
	physicalUpdateCanvas(canvas)
	if v then coroutine.yield() end
	
	return v
end
local function applyNodeStart(canvas, node)
	applyNode(canvas, node)
	setCurrentNodeBricks({})
end
applyNodeTypes = {
	sequence = function(canvas, node)
		local i = 0
		for _, subNode in ipairs(node.subNodes) do
			if subNode.limitmin then
				subNode.limit = math.random(subNode.limitmin, subNode.limitmax)
			end
			local j = 0;
			while
				(subNode.limit == nil or j < subNode.limit) and
				applyNode(canvas, subNode)
			do
				i = i+1; j = j+1;
			end
			if node.limittemp then node.limit = nil; talk("clear limit") end
		end
		return i > 0
	end,
	markov = function(canvas, node)
		local i = 0
		for _, subNode in ipairs(node.subNodes) do
			if applyNode(canvas, subNode) then i = i+1; break; end
		end
		return i > 0
	end,
	choice = function(canvas, node)
		local success = false
		while true do
			local subNode = selectByWeight(node.subNodes)
			if subNode then
				local status = applyNode(canvas, subNode)
				if status then
					success = true
					break
				else
					subNode.choiceIgnore = true
				end
			else
				break
			end
		end
		for _, subNode in ipairs(node.subNodes) do
			subNode.choiceIgnore = nil
		end
		return success
	end,
	wfc = function(canvas, node)
		error("WFC not implemented")
	end,
	def = function(canvas, node)
		if not node.pattern then error("Node has no pattern") end
		
		local spots = matchPattern(canvas, node.pattern)
		if node.limitpercent and not node.limit then
			node.limit = math.ceil(#spots * node.limitpercent / 100)
			node.limittemp = true
			talk("set limit to "..node.limit)
		end
		if #spots > 0 then
			local spot = spots[math.random(1, #spots)]
			applyReplacement(canvas, spot, node.pattern, node.replace)
			return true
		else
			return false
		end
	end,
}

---------------------------------------------

local function getRealBricksInBox(allRealBricks, boxAbsTU)
	local realBricks = {}
	for _, realBrick in pairs(allRealBricks) do
		if posIsInBox(boxAbsTU, realBrick.posAbsTU) then
			table.insert(realBricks, realBrick)
		end
	end
	return realBricks
end
local function createCanvasInBoxAbsTU(allRealBricks, boxAbsTU)
	local canvas = {
		boxAbsTU = boxAbsTU,
		realBricksByRealBrickString = {},
		filledSpaceByPosAbsTUString = {},
		physicalRealBricks = {},
		realBricksByPartialString = {},
	}
	for _, realBrick in ipairs(getRealBricksInBox(allRealBricks, boxAbsTU)) do
		canvasInsertRealBrick(canvas, realBrick)
		canvas.physicalRealBricks[realBrick.realBrickString] = realBrick
	end
	return canvas
end

local function createDefBrickFromRealBrick(realBrick, posAbsTU)
	local defBrick = {
		posRelTU = realBrick.posAbsTU - posAbsTU,
		angleIdRel = realBrick.angleIdAbs,
		color = realBrick.color,
		colorFx = realBrick.colorFx,
		loadStringRotationAngleId = realBrick.loadStringRotationAngleId,
		staticData = realBrick.staticData,
	}
	return defBrick
end
local function getBrickById(allRealBricks, brickId)
	local realBrick = allRealBricks[brickId]
	assert(realBrick)
	return realBrick
end
local brickMask = ts.get("TypeMasks::FxBrickObjectType")
local function getAdjacentBricks(allRealBricks, realBrick)
	local boxAbsTU = getRealBrickBoxAbsTU(realBrick)
	ts.call("initContainerBoxSearch",
		realBrick.posAbsTU:tsString(),
		(boxAbsTU[2] - boxAbsTU[1] + adjacentBrickBoxExpansion):tsString(),
		brickMask
	)
	local adjacentBricks = {}
	while true do
		local nextBrickId = tonumber(ts.call("containerSearchNext"))
		if not ts.isObject(nextBrickId) then break end
		table.insert(adjacentBricks, getBrickById(allRealBricks, nextBrickId))
	end
	return adjacentBricks
end
local function getContiguousBricksRecurse(allRealBricks, bricksById, realBrick, minZ)
	bricksById[realBrick.brickId] = realBrick
	local adjacentBricks = getAdjacentBricks(allRealBricks, realBrick)
	for _, adjacentBrick in ipairs(adjacentBricks) do
		if bricksById[adjacentBrick.brickId] == nil and adjacentBrick.posAbsTU.z >= minZ then
			bricksById[adjacentBrick.brickId] = adjacentBrick
			getContiguousBricksRecurse(allRealBricks, bricksById, adjacentBrick, minZ)
		end
	end
end
local function getContiguousBricksAbove(allRealBricks, realBrick, minZ)
	local bricksById = {}
	getContiguousBricksRecurse(allRealBricks, bricksById, realBrick, minZ)
	local bricks = {}
	for _, brick in pairs(bricksById) do table.insert(bricks, brick) end
	return bricks
end
local dirsByAngleId = {
	[0] = vector{ 0,  1,  0},
	[2] = vector{ 0, -1,  0},
	[1] = vector{ 1,  0,  0},
	[3] = vector{-1,  0,  0},
	[4] = vector{ 0,  0,  1},
	[5] = vector{ 0,  0, -1},
}
local angleIdsByName = {
	north = 0, east = 1, south = 2, west = 3, up = 4, down = 5,
}
local function rotateAngleId(angleId, rot)
	if angleId<=3 then return (angleId + rot) % 4 else return angleId end
end

local function getNonignoredBrickFromRay(allRealBricks, pos1, pos2, dirVec, ignoreBrickIds, lastBrickId)
	local ray = ts.call("containerRaycast", pos1:tsString(), pos2:tsString(), brickMask, lastBrickId)
	local hitBrickIdStr, hitPosStr, hitNormStr = ray:match("^([^ ]+) ([^ ]+ [^ ]+ [^ ]+) ([^ ]+ [^ ]+ [^ ]+)$")
	if hitBrickIdStr then
		local hitBrickId, hitPos, hitNorm = tonumber(hitBrickIdStr), vector(hitPosStr), vector(hitNormStr)
		if ignoreBrickIds[hitBrickId] then
			return getNonignoredBrickFromRay(allRealBricks, hitPos + dirVec*0.1, pos2, dirVec, ignoreBrickIds, hitBrickId)
		else
			return getBrickById(allRealBricks, hitBrickId), hitPos
		end
	else
		return nil
	end
end
local function getNonignoredBrickInDirection(allRealBricks, realBrick, dirName, distance, ignoreBrickIds)
	local dirVec = dirsByAngleId[rotateAngleId(angleIdsByName[dirName], realBrick.angleIdAbs)]
	return getNonignoredBrickFromRay(allRealBricks, realBrick.posAbsTU, realBrick.posAbsTU + dirVec*distance, dirVec, ignoreBrickIds, realBrick.brickId)
end
local function getBrickInDirection(allRealBricks, realBrick, dirName, distance)
	return getNonignoredBrickInDirection(allRealBricks, realBrick, dirName, distance, {})
end
local function getAdjacentTreeBrick(allRealBricks, realBrick, dirName)
	local adjacentBrick = getBrickInDirection(allRealBricks, realBrick, dirName, 0.5)
	if adjacentBrick and adjacentBrick.staticData.uiName == "1x1F Print" and adjacentBrick.angleIdAbs == realBrick.angleIdAbs then
		return adjacentBrick
	else
		return nil
	end
end
local function addBrickToSpaces(realBrick, spacesRelTU, posRootTU)
	for _, posAbsTU in ipairs(getAllPosInBoxAbsTU(getRealBrickBoxAbsTU(realBrick))) do
		local posRelTU = posAbsTU - posRootTU
		table.insert(spacesRelTU, posRelTU)
	end
end
local printNames = {
	["and"] = "&", apostrophe = "\'", asterisk = "*", at = "@", bang = "!", caret = "^", dollar = "$", equals = "=",
	greater_than = ">", less_than = "<", minus = "-", percent = "%", period = ".", plus = "+", pound = "#", qmark = "?",
	space = " ", apostrophe2 = "\"", colon = ":", comma = ",", curlybracketleft = "}", curlybracketright = "{", roundbracketleft = ")",
	roundbracketright = "(", slashleft = "\\", slashright = "/", squarebracketleft = "]", squarebracketright = "[", tile = "~",
	underscore = "_", verticalbar = "|", backtick = "`", semicolon = ";",
}
local function letterFromPrintName(printName)
	local letter = printName:match("Letters/(.+)$")
	if not letter then return nil end
	if #letter==1 then return letter end
	if letter:sub(2, #letter)=="lcase" then return letter:sub(1, 1):lower() end
	if letter:sub(1, 1)=="-" then return printNames[letter:sub(2, #letter)] end
	return nil
end
local function getTextFromPrintBrick(allRealBricks, currBrick)
	local printName = currBrick.staticData.printName
	local letter = letterFromPrintName(printName)
	if letter then
		local nextBrick = getBrickInDirection(allRealBricks, currBrick, "east", 0.5)
		if nextBrick then
			return letter..getTextFromPrintBrick(allRealBricks, nextBrick)
		else
			return letter
		end
	else
		return ""
	end
end
local function applyTextToNode(text, node)
	if text:find("^[0-9]+$") then
		node.limit = tonumber(text); return true;
	elseif text:find("^[0-9]+%%$") then
		node.limitpercent = tonumber(text:sub(1, #text-1)); return true;
	elseif text:find("^[0-9]+W$") then
		node.weight = tonumber(text:sub(1, #text-1)); return true;
	elseif text:find("^[0-9]+%-[0-9]+$") then
		local lm, lx = text:match("^([0-9]+)%-([0-9]+)$")
		lm, lx = tonumber(lm), tonumber(lx)
		if lm and lx then
			node.limitmin = lm; node.limitmax = lx;
			return true;
		end
	end
	if text:find("[^ ]") then talk("Invalid text \""..text.."\"") end
end
local function tablesHaveSameKeys(t1, t2)
	for k, v in pairs(t1) do
		if t2[k] == nil then return false end
	end
	for k, v in pairs(t2) do
		if t1[k] == nil then return false end
	end
	return true
end
local function createDefNodeFromBrick(allRealBricks, realBrick, ignoreBrickIds, treeBrickIds)
	local rightBrick, rightBrickHitPos = getBrickInDirection(allRealBricks, realBrick, "east", maxTemplateWidth)
	if (not rightBrick) or ignoreBrickIds[rightBrick.brickId] then return nil end
	
	if rightBrick.angleId ~= realBrick.angleId then return nil, "rightBrick has wrong orientation" end
	
	local node = {
		type = "def",
		weight = 100,
		limit = nil,
		treeBrickIds = copy(treeBrickIds),
		pattern = {
			defBricks = {},
			spacesRelTU = {},
			fillsRelTU = {},
			replaceSpacesRelTU = {},
		},
		replace = {
			defBricks = {},
		},
	}
	
	local patternSpaces = node.pattern.replaceSpacesRelTU
	local replaceSpaces = {}
	
	-- construct pattern
	local contBricks = getContiguousBricksAbove(allRealBricks, rightBrick, rightBrick.posAbsTU.z - 0.1)
	for _, contBrick in ipairs(contBricks) do
		if contBrick.color ~= colorSpace and contBrick.colorFx ~= colorFxIgnore and contBrick.colorFx ~= colorFxFill then
			rootBrick = contBrick
			break
		end
	end
	if not rootBrick then return nil, "All pattern bricks are empty space" end
	
	node.pattern.rootBrick = rootBrick
	local posRootTU = rootBrick.posAbsTU
	
	for _, contBrick in ipairs(contBricks) do
		if contBrick.color == colorSpace then
			addBrickToSpaces(contBrick, node.pattern.spacesRelTU, posRootTU)
		elseif contBrick.colorFx == colorFxFill then
			addBrickToSpaces(contBrick, node.pattern.fillsRelTU, posRootTU)
		elseif contBrick.colorFx ~= colorFxIgnore then
			local defBrick = createDefBrickFromRealBrick(contBrick, posRootTU)
			table.insert(node.pattern.defBricks, defBrick)
		end
		addBrickToSpaces(contBrick, patternSpaces, posRootTU)
		ignoreBrickIds[contBrick.brickId] = true
	end
	
	-- construct replace
	local rightBrick2, rightBrick2HitPos = getNonignoredBrickInDirection(allRealBricks, realBrick, "east", maxTemplateWidth, ignoreBrickIds)
	if not rightBrick2 then return nil, "Could not find replacement template" end

	if rightBrick2.angleId ~= realBrick.angleId then return nil, "rightBrick2 has wrong orientation" end
	local posRootTU2 = posRootTU - rightBrickHitPos + rightBrick2HitPos
	local contBricks2 = getContiguousBricksAbove(allRealBricks, rightBrick2, rightBrick.posAbsTU.z - 0.1)
	for _, contBrick in ipairs(contBricks2) do
		if contBrick.color ~= colorSpace then
			local defBrick = createDefBrickFromRealBrick(contBrick, posRootTU2)
			table.insert(node.replace.defBricks, defBrick)
		end
		addBrickToSpaces(contBrick, replaceSpaces, posRootTU)
		ignoreBrickIds[contBrick.brickId] = true
	end
	
	if not tablesHaveSameKeys(patternSpaces, replaceSpaces) then return nil, "Pattern and replacement have different shapes" end
	
	local rightBrick3 = getNonignoredBrickInDirection(allRealBricks, realBrick, "east", maxTemplateWidth, ignoreBrickIds)
	if rightBrick3 and rightBrick3.staticData.uiName == "1x1F Print" then
		local text = getTextFromPrintBrick(allRealBricks, rightBrick3)
		applyTextToNode(text, node)
	end
	
	return node
end

local createNodeFromBrick
local function createSubNodeFromBrick(allRealBricks, realBrick, ignoreBrickIds, treeBrickIds)
	local rightBrick = getAdjacentTreeBrick(allRealBricks, realBrick, "east")
	if rightBrick then
		local rightRightBrick = getAdjacentTreeBrick(allRealBricks, rightBrick, "east")
		if rightRightBrick then
			local rightTreeBrickIds = copy(treeBrickIds)
			rightTreeBrickIds[rightBrick.brickId] = true
			rightTreeBrickIds[rightRightBrick.brickId] = true
			local subNode, err = createNodeFromBrick(allRealBricks, rightRightBrick, ignoreBrickIds, rightTreeBrickIds)
			if subNode then
				local text = getTextFromPrintBrick(allRealBricks, realBrick)
				text = text:gsub(" +", "")
				if text ~= "" then applyTextToNode(text, subNode) end
				return subNode
			else
				return nil, "subNode: "..err
			end
		else
			return nil, "Right brick with no subtree"
		end
	else
		return nil
	end
end
local nodeTypesByColor = {
	[32] = "sequence",
	[24] = "markov",
	[30] = "choice",
}
createNodeFromBrick = function(allRealBricks, realBrick, ignoreBrickIds, treeBrickIds)
	assert(realBrick.staticData.uiName == "1x1F Print")
	--[[node = {
		type = one of "sequence", "markov", "choice", "wfc", "def"
		if not def: subNodes = list of node
		if parent is choice: weight (for choice parent node)
		if parent is sequence: limit (number of times to run)
		treeBrickIds = dict of brickId -> true
		if def:
			pattern = {
				defBricks = list of defBrick
				spacesRelTU = list of vector
				rootBrick
			}
			replace = {
				defBricks = list of defBrick
			}
	}]]
	
	local nodeType = nodeTypesByColor[realBrick.color]
	if not nodeType then return nil, "Invalid color "..realBrick.color end
	
	local node = {
		type = nodeType,
		subNodes = {},
		treeBrickIds = copy(treeBrickIds),
		weight = 100,
	}
	
	local downBrick = realBrick
	local lengthDown = 0
	while downBrick do
		node.treeBrickIds[downBrick.brickId] = true
		ignoreBrickIds[downBrick.brickId] = true
		
		local subNode, err = createSubNodeFromBrick(allRealBricks, downBrick, ignoreBrickIds, node.treeBrickIds)
		if subNode then
			table.insert(node.subNodes, subNode)
		elseif err then
			return nil, "downBrick "..lengthDown.." subNode: "..err
		else
			local defNode, err = createDefNodeFromBrick(allRealBricks, downBrick, ignoreBrickIds, node.treeBrickIds)
			if defNode then
				table.insert(node.subNodes, defNode)
			elseif err then
				return nil, "downBrick "..lengthDown.." defNode: "..err
			end
		end
		lengthDown = lengthDown + 1
		downBrick = getAdjacentTreeBrick(allRealBricks, downBrick, "south")
	end
	
	return node
end
local function getNodesFromRealBricks(allRealBricks)
	local nodes = {}
	
	local ignoreBrickIds = {}
	for _, realBrick in pairs(allRealBricks) do
		if realBrick.staticData.uiName == "1x1F Print" and realBrick.staticData.ntName and realBrick.staticData.ntName:find("^node") then
			local nodeName = realBrick.staticData.ntName:match("^node_(.+)$")
			if nodes[nodeName] then
				talk("Node with name "..nodeName.." already exists")
			else
				local rightBrick = getAdjacentTreeBrick(allRealBricks, realBrick, "east")
				if rightBrick then
					local treeBrickIds = {}
					local node, err = createNodeFromBrick(allRealBricks, rightBrick, ignoreBrickIds, treeBrickIds)
					if not node then
						talk("Error creating node for brick "..realBrick.brickId..": "..err)
					else
						nodes[nodeName] = node
					end
				else
					talk("Error: Node name "..nodeName.." does not point to a tree")
				end
			end
		end
	end
	
	return nodes
end

ts.eval [[
$MJ_NDSymmetryConversion[0] = 4;
$MJ_NDSymmetryConversion[1] = 2;
$MJ_NDSymmetryConversion[2] = 4;
$MJ_NDSymmetryConversion[3] = 4;
$MJ_NDSymmetryConversion[4] = 4;
$MJ_NDSymmetryConversion[5] = 4;
function fxDtsBrickData::mj_computeSymmetry(%data) {
	%file = new FileObject();
	%file.openForRead(%data.brickFile);
	
	%size = %file.readLine();
	%type = %file.readLine();
	%isBrick = %type $= "BRICK";
	if(%isBrick) {
		if(%data.brickSizeX == %data.brickSizeY) {
			%sym = 1;
		} else {
			%sym = 2;
		}
	} else {
		%sym = 4;
	}
	
	%file.close();
	%file.delete();
	
	if(%sym == 4) {
		%sym2 = $MJ_NDSymmetryConversion[ $ND::Symmetry[%data.getId()] ];
		if(%sym2 !$= "") %sym = %sym2;
	}
	
	return %sym;
}
function fxDtsBrickData::mj_getSymmetry(%data) {
	//if(%data.mj_symmetry !$= "") return %data.mj_symmetry;
	%sym = %data.mj_computeSymmetry();
	%data.mj_symmetry = %sym;
	return %sym;
}
function fxDtsBrickData::getUiName(%data) { return %data.uiName; }
function fxDtsBrickData::getBrickSize(%data) { return %data.brickSizeX SPC %data.brickSizeY SPC %data.brickSizeZ; }
]]
local getUiName = memoize(function(brickdata) return ts.callobj(brickdata, "getUiName") end)
local studSizeTU = vector{0.5, 0.5, 0.2}
local getBrickSizeTU = memoize(function(brickdata) return vector(ts.callobj(brickdata, "getBrickSize")) * studSizeTU end)
local getSymmetry = memoize(function(brickdata) return tonumber(ts.callobj(brickdata, "mj_getSymmetry")) end)
local function getDatablock(brick) return ts.callobj(brick, "getDatablock") end
local function getAngleId(brick) return tonumber(ts.callobj(brick, "getAngleId")) end
local function getNtName(brick) local name = ts.callobj(brick, "getName"); if name == "" then return nil else return name:sub(2, #name) end; end
local function getColor(brick) return tonumber(ts.callobj(brick, "getColorId")) end
local function getColorFx(brick) return tonumber(ts.callobj(brick, "getColorFxId")) end
local function getPrintName(brick) local name = ts.callobj(brick, "getPrintName"); if name == "" then return nil else return name end; end
local function getAllRealBricks()
	local allRealBricks = {}
	
	for brickId in ts.allBricks() do
		local brickData = getDatablock(brickId)
		local realBrick = {
			brickId = brickId,
			posAbsTU = ts.getPosition(brickId),
			angleIdAbs = getAngleId(brickId),
			loadStringRotationAngleId = 0,
			color = getColor(brickId),
			colorFx = getColorFx(brickId),
			staticData = {
				originalBrickId = brickId,
				uiName = getUiName(brickData),
				brickSizeTUUnrotated = getBrickSizeTU(brickData),
				symmetry = getSymmetry(brickData),
				ntName = getNtName(brickId),
				printName = getPrintName(brickId),
			}
		}
		
		assert(realBrick.brickId)
		assert(realBrick.posAbsTU)
		assert(realBrick.loadStringRotationAngleId)
		assert(realBrick.color)
		assert(realBrick.colorFx)
		assert(realBrick.staticData.originalBrickId)
		assert(realBrick.staticData.uiName)
		assert(realBrick.staticData.brickSizeTUUnrotated)
		assert(realBrick.staticData.symmetry)
		
		realBrick.realBrickString = realBrickGetString(realBrick)
		realBrick.partialString = realBrickGetPartialString(realBrick)
		allRealBricks[realBrick.brickId] = realBrick
	end
	
	return allRealBricks
end

local function getData()
	local canvasBoxAbsTU = {
		vector{-8, -8,  0.2},
		vector{ 8,  8, 16.2},
	}
	
	local allRealBricks = getAllRealBricks()
	local canvas = createCanvasInBoxAbsTU(allRealBricks, canvasBoxAbsTU)
	local nodes = getNodesFromRealBricks(allRealBricks)
	local node = nodes["test"]
	if not node then talk("No node named node_test") end
	
	return canvas, node
end

-----------------

local function applyNodesAll()
	local canvas, node = getData()
	if not (canvas and node) then
		return
	end
	
	--local s = tabletostring(node, true)
	--for l in s:gmatch("[^\n]+") do talk(l) end
	
	applyNodeStart(canvas, node)
end

if not exists("MarkovJunior_Data") then MarkovJunior_Data = { cor = nil, treeBricks = {} } end
function MarkovJunior_Start()
	MarkovJunior_Data.cor = coroutine.create(applyNodesAll)
	talk("Started")
end
function MarkovJunior_Advance(steps)
	steps = tonumber(steps) or 1
	for i = 1, steps do
		if MarkovJunior_Data.cor then
			local status, err = coroutine.resume(MarkovJunior_Data.cor)
			if not status then
				if err ~= "cannot resume dead coroutine" then
					talk(err)
					talk(debug.traceback(MarkovJunior_Data.cor))
				end
				MarkovJunior_Data.cor = nil
				return false
			end
		end
	end
	return true
end

ts.eval [[
	function fxDtsBrick::getMJGenerated(%brick) { return %brick.mjGenerated; }
]]
function MarkovJunior_Clear()
	local toRemove = {}
	for brick in ts.allBricks() do
		if ts.callobj(brick, "getMJGenerated") == "1" then
			table.insert(toRemove, brick)
		end
	end
	for _, brick in ipairs(toRemove) do
		ts.callobj(brick, "delete")
	end
	talk("Cleared "..#toRemove.." generated bricks")
end

ts.eval [[
	function serverCmdMJStart(%c) {
		if(%c.isAdmin) {
			luacall("MarkovJunior_Start");
			MJ_Loop();
		}
	}
	function serverCmdMJT(%c) {
		if(%c.isAdmin) {
			if($MJ_Enabled) {
				$MJ_Enabled = 0;
			} else {
				$MJ_Enabled = 1;
				MJ_Loop();
			}
			talk("MJ " @ ($MJ_Enabled ? "Enabled" : "Disabled"));
		}
	}
	function serverCmdMJS(%c) {
		if(%c.isAdmin) {
			%cont = luacall("MarkovJunior_Advance", 1);
			talk(%cont ? "Advanced" : "Done");
		}
	}
	function serverCmdMJClear(%c) {
		if(%c.isAdmin) {
			luacall("MarkovJunior_Clear");
		}
	}
	function MJ_Loop() {
		if(!$MJ_Enabled) return;
		
		%cont = luacall("MarkovJunior_Advance", $MJ_Speed);
		
		cancel($MJ_Sched);
		if(%cont) {
			$MJ_Sched = schedule(33, 0, MJ_Loop);
		} else {
			talk("Done");
		}
	}
	
	function mjr() { exec("Add-ons/Server_MarkovJunior/server.cs"); }
]]
